package com.atguigu.algorithm;

import java.util.Scanner;

public class Fibonacci {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int[] helper=new int[100002];
        helper[0]=1;
        helper[1]=1;
        for(int i=2;i<helper.length;i++){
            helper[i]=helper[i-1]+helper[i-2];
            helper[i]=helper[i]%1000000;
        }
        while(scanner.hasNextInt()){
            int n=scanner.nextInt();
            if(n<29) {
                System.out.println(helper[n]);
            }else{
                StringBuilder sb=new StringBuilder();
                String string=String.valueOf(helper[n]);
                int tmp=6;
                while(tmp-string.length()>0){
                    sb.append(0);
                    tmp--;
                }
                sb.append(string);
                System.out.println(sb.toString());
            }
        }
    }
}
